package com.singzi.leetcode.N100;

public class T0034 {
}
class Solution0034 {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[]result = {-1,-1};
        if(n == 1){
            if(nums[0] == target){
                result[0] = 0;
                result[1] = 0;
            }
            else return result;
        }
        int flag = -1;
        int left = 0, right = n-1;
        while (left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid+1;
            }else if(nums[mid] > target){
                right = mid-1;
            }else {
                flag = mid;
                break;
            }
        }
        if(flag!=-1){
            result[0] = binarySearchLeft(nums, 0, flag, target);
            result[1] = binarySearchRight(nums, flag, n-1, target) -1;
        }
        return result;
    }
    public int binarySearchLeft(int[]nums, int left, int right, int target){
        while (left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target) right = mid - 1;
            else left = mid+1;
        }
        return left;
    }
    public int binarySearchRight(int[]nums, int left, int right, int target){
        while (left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target) right = mid - 1;
            else left = mid+1;
        }
        return left;
    }

}